/*
 *https://leetcode.cn/problems/magnetic-force-between-two-balls/
 *1552. 两球之间的磁力
 *medium 吴朝泽 2024.9.11
 *二分查找
check 函数的作用是判断在给定的最小磁力 x 下，最多可以放置多少个球。具体操作是：
从第一个位置开始放置第一个球。
遍历后续位置，只有当当前位置与上一个放置球的位置之间的距离至少为 x 时，才放置下一个球。
返回能够成功放置的球的数量。
如果 check(position, mid) >= m，说明在磁力值 mid 下可以放置 m 个球，
因此可以尝试更大的磁力值。更新左边界 l = mid + 1。
如果 check(position, mid) < m，说明在磁力值 mid 下无法放置 m 个球，
需要尝试更小的磁力值。更新右边界 r = mid - 1。
*/

class Solution {
public:
    //找到某个最小磁力时，最多能放的球的个数
    int check(vector<int>& psn, int x)
    {
        int pre = psn[0];
        int count = 1;
        for(int i = 0; i < psn.size(); ++i)
        {
            if(psn[i] - pre >= x)
            {
                pre = psn[i];
                count++;
            }
        }
        return count;
    }

    int maxDistance(vector<int>& position, int m) 
    {
        sort(position.begin(),position.end());
        int l = 1, r = position[n-1];
        while(l <= r)
        {
            int mid = (l + r) / 2;
            if(check(position,mid) >= m)  l = mid + 1;
            else  r = mid - 1;
        }
        return r;
    } 
};